/* Copyright (C) 1997-2005, Antony L Hosking.
 * All rights reserved.  */
package RegAlloc;

import java.util.*;

import Translate.Frame;
import Translate.Temp;
import Translate.Tree;
import Translate.Tree.Exp.*;
import Translate.Tree.Stm.*;
import Assem.Instr;

public class RegAlloc implements Temp.Map {
    FlowGraph.AssemFlowGraph cfg;
    Liveness ig;
    public Temp[] spills;
    Color color;

    public Temp get(Temp temp) {
        Temp t = ig.get(temp).color;
        if (t == null)
            t = temp;
        return t;
    }
    
    private void RewriteProgram(Translate.Frame frame, LinkedList<Instr> insns){
    	LinkedHashSet<Temp> spillSet = new LinkedHashSet<Temp>(Arrays.asList(spills));
    	HashMap<Temp, Translate.Frame.Access> spillMap = new HashMap<Temp,  Translate.Frame.Access>();
    	//Allocate frame space for each spilled Temp
    	for(Temp t : spillSet) {
    		spillMap.put(t, frame.allocLocal(null));
    	}
    	
    	ListIterator<Instr> iter = insns.listIterator();
    	Instr insn = null;
    	while(iter.hasNext()) {
    		insn = iter.next();
    		for(int i = 0; i < insn.use.length; i++) {
    			Translate.Temp oldTemp = insn.use[i];
    			if(spillSet.contains(oldTemp)) {
    				Translate.Temp tempUse = new Translate.Temp();
    				insn.replaceUse(oldTemp, tempUse);
    				
    				//Insert fetch instructions
        			iter.previous();
        			Translate.Frame.Access acc = spillMap.get(oldTemp);
        			Translate.Frame.CodeGen codeGen = frame.codegen();
        			Translate.Tree.Stm.MOVE moveStmt = new Translate.Tree.Stm.MOVE(new Translate.Tree.Exp.TEMP(tempUse), acc.exp(frame.FP()));
        			codeGen.visit(moveStmt);
        			for(Instr newInstr : codeGen.insns()) {
        				iter.add(newInstr);
        			}
        			iter.next();
    			}
    		}
	    	for(int i = 0; i < insn.def.length; i++) {
	    		Translate.Temp oldTemp = insn.def[i];
				if(spillSet.contains(oldTemp)) {
					Translate.Temp tempDef = new Translate.Temp();
					insn.replaceDef(oldTemp, tempDef);
					
					//Insert store instructions
        			Translate.Frame.Access acc = spillMap.get(oldTemp);
        			Translate.Frame.CodeGen codeGen = frame.codegen();
        			Translate.Tree.Stm.MOVE moveStmt = new Translate.Tree.Stm.MOVE(acc.exp(frame.FP()), new Translate.Tree.Exp.TEMP(tempDef));
        			codeGen.visit(moveStmt);
        			for(Instr newInstr : codeGen.insns()) {
        				iter.add(newInstr);
        			}
				}
			}
    	}
    }

    public RegAlloc(Translate.Frame frame, LinkedList<Instr> insns,
            java.io.PrintWriter out) {
        for (;;) {
            out.println("# Control Flow Graph:");
            cfg = new FlowGraph.AssemFlowGraph(frame, insns);
            cfg.show(out);
            out.println("# Interference Graph:");
            ig = new Liveness(cfg, frame);
            ig.show(out);
            color = new Color(ig, frame);
            spills = color.spills();
            if (spills == null)
                break;
            out.println("# Spills:");
            for (Temp s : spills)
                out.println(s);
            // Rewrite the program and do spilling!
            RewriteProgram(frame, insns);
        }
        out.println("# Register Allocation:");
        for (Node n : ig.nodes()) {
            out.print(n.temp);
            out.print("->");
            out.println(n.color);
        }
    }
}
